{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.6 Shor's Algorithm\n",
    "\n",
    "Shor's algorithm was invented by Peter Shor in 1994 as a quantum computing algorithm to efficiently find prime factors of an integer. It is an important algorithm because the current widely used RSA cryptography scheme relies on the fact that large integers take unfeasible amount of time to factor on classical computers. With Shor's algorithm implemented when quantum computers are ready, existing cryptography will be broken.\n",
    "\n",
    "Let's say there are two large prime numbers $\\textit{p}$ and $\\textit{q}$. You are given the product of them $\\textit{p}$.$\\textit{q}$, not the individual $\\textit{p}$ and $\\textit{q}$. If $\\textit{p}$.$\\textit{q}$ is a small number, you can calculate possible values of $\\textit{p}$ and $\\textit{q}$. But if the product is large, there is no classical algorithm invented so far to give the components $\\textit{p}$ and $\\textit{q}$ in polynomial time. That is, if we try to factor a 2048 bit number which is a product of two large prime numbers, it will take more than the age of the universe even if you use the fastest supercomputer. However, using the Shor's algorithm, we can do it within in a few hours provided we have a quantum computer with a few thousand qubits.\n",
    "\n",
    "To demonstrate this algorithm, let's take $\\textit{N}$= 35 as the number we want to factorize, and we want to know $\\textit{p}$ and $\\textit{q}$ that this $\\textit{N}$ is composed of.\n",
    "\n",
    "$\\textbf{Step 1:}$\n",
    "\n",
    "Pick a random number $\\textit{a}$ between 2 and $\\textit{N}$ − 1 and take the greatest common denominator (GCD) with $\\textit{N}$. We need to remember that GCD of large numbers can be found in polynomial time using Euclidean algorithm. If the GCD does not equal to 1 (GCD != 1), then we can say that the GCD is one of the factor and we find the solution. For example, if we had chosen $\\textit{a}$ = 10 , then GCD (10, 35) = 5. Since it is not equal to 1, then 5 must be the factor. However, the probability of finding this random number to be the solution is extremely low. If we took $\\textit{a}$ = 3, then GCD (3,35) = 1, i.e. $\\textit{a}$ and $\\textit{N}$ are co-primes.\n",
    "\n",
    "$\\textbf{Step 2:}$\n",
    "\n",
    "Find some number $\\textit{Q}$ = $2^q$ such that $\\textit{Q}$ is the first power of 2 greater than or equal to $\\textit{N}^2$. In this example $\\textit{N}^2$ = $35^2$ = 1225; so $\\textit{Q}$ = 2048 and $\\textit{q}$ = 11.\n",
    "\n",
    "$\\textbf{Step 3:}$\n",
    "\n",
    "Evaluate the expression $\\textit{a}^x  Mod  \\textit{N}$ for all $\\textit{x}$ ranging from 0 to $\\textit{Q}$ − 1\n",
    "\n",
    "<table width=\"400px\">\n",
    "  <tr>\n",
    "    <th> $ x $ </th>\n",
    "    <th> $ 3^x Mod 35 $ </th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 0 </td>\n",
    "    <td> 1 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 1 </td>\n",
    "    <td> 3 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 2 </td>\n",
    "    <td> 9 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 3 </td>\n",
    "    <td> 27 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 4 </td>\n",
    "    <td> 11 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 5 </td>\n",
    "    <td> 33 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 6 </td>\n",
    "    <td> 29 </td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td> 7 </td>\n",
    "    <td> 17 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 8 </td>\n",
    "    <td> 16 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 9 </td>\n",
    "    <td> 13 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 10 </td>\n",
    "    <td> 4 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 11 </td>\n",
    "    <td> 12 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 13 </td>\n",
    "    <td> 3 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 14 </td>\n",
    "    <td> 9 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 15 </td>\n",
    "    <td> 27 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 16 </td>\n",
    "    <td> 1 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 17 </td>\n",
    "    <td> 33 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 18 </td>\n",
    "    <td> 29 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 19 </td>\n",
    "    <td> 17 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 20 </td>\n",
    "    <td> 16 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 21 </td>\n",
    "    <td> 13 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 22 </td>\n",
    "    <td> 4 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 23 </td>\n",
    "    <td> 12 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 24 </td>\n",
    "    <td> 1 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 25 </td>\n",
    "    <td> 3 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 26 </td>\n",
    "    <td> 9 </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> . </td>\n",
    "    <td> - </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> . </td>\n",
    "    <td> - </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> . </td>\n",
    "    <td> . </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> . </td>\n",
    "    <td> . </td>\n",
    "  </tr>\n",
    "      <tr>\n",
    "    <td> 2047 </td>\n",
    "    <td> 17 </td>\n",
    "  </tr>\n",
    "</table>\n",
    "<center>$Table 2.6.1$</center>\n",
    "$\\textbf{Step 4:}$\n",
    "\n",
    "As you can see in Step 3, the period, $\\textit{r}$, is 12 in this case.\n",
    "\n",
    "$\\textbf{Step 5:}$\n",
    "\n",
    "We observe the following:\n",
    "\n",
    "<center>$\\textit{a}^0  \\textit{Mod N} = 3^0 \\textit{Mod} 35 = \\textit{a}^\\textit{r} \\textit{Mod N} = 3^12 \\textit{Mod} 35 = 1$,</center>\n",
    "\n",
    "which means that $\\textit{a}^\\textit{r}$ is the first non-zero number when divided by $\\textit{N}$ gives the reminder 1. We can say that $\\textit{a}^\\textit{r}$ - 1 will be divisible by $\\textit{N}$. This is written as $\\textit{N} | \\textit{a}^\\textit{r}$ - 1 (read as $\\textit{N}$ divides $\\textit{a}^\\textit{r}$ - 1). If r is even, then we can rewrite it as follows:\n",
    "\n",
    "\n",
    "<center>$\\textit{N}\\hspace{0.4em} |\\hspace{0.4em} \\textit{a}^\\textit{r} - 1^2 $</center>\n",
    "\n",
    "<center>$\\textit{N}\\hspace{0.4em} |\\hspace{0.4em} (\\textit{a}^\\textit{r/2})^2 - 1^2 $</center>\n",
    "\n",
    "<center>$\\textit{N}\\hspace{0.4em} |\\hspace{0.4em} (\\textit{a}^\\textit{r/2} -1)(\\textit{a}^\\textit{r/2} +1)(because \\hspace{0.4em} \\textit{a}^2 - \\textit{b}^2 = (\\textit{a}-\\textit{b})(\\textit{a}+\\textit{b}))$.</center>\n",
    "\n",
    "\n",
    "\n",
    "If $\\textit{r}$ turns out to be odd, then we need to repeat Step 1 by picking another $\\textit{a}$. Also, if $\\textit{N}\\hspace{0.4em} |\\hspace{0.4em} (\\textit{a}^\\textit{r/2} +1)$, we need to discard $\\textit{r}$ and repeat Step 1. It will be clear soon why we need to do these.\n",
    "\n",
    "In addition, we clearly know that $\\textit{N}\\hspace{0.4em} |\\hspace{0.4em} (\\textit{a}^\\textit{r/2} -1)$ will never be the case because $\\textit{r}$ is the smallest number with the property $\\textit{N}\\hspace{0.4em} |\\hspace{0.4em} (\\textit{a}^\\textit{r} -1)$ by definition.\n",
    "\n",
    "Now that we have established that $\\textit{N}\\hspace{0.4em} |\\hspace{0.4em} (\\textit{a}^\\textit{r/2} -1)(\\textit{a}^\\textit{r/2} +1)$ but is not divisible with either of the terms separately, it can only mean that one of the factor, $\\textit{p}$, divides $(\\textit{a}^\\textit{r/2}-1)$ and another factor, $\\textit{q}$, divides $(\\textit{a}^\\textit{r/2}+1)$.\n",
    "\n",
    "So, $\\textit{p}$ will be a common divisor of $\\textit{N}$ and $(\\textit{a}^\\textit{r/2} -1)$, and $\\textit{q}$ will be a common divisor of $\\textit{N}$ and $(\\textit{a}^\\textit{r/2} +1)$. To get the values of $\\textit{p}$ and $\\textit{q}$, we simply need to find GCD( $\\textit{N}$ , $(\\textit{a}^\\textit{r/2}-1)$) to get $\\textit{p}$ and find GCD( $\\textit{N}$ , $(\\textit{a}^\\textit{r/2}+1)$) to get $\\textit{q}$.\n",
    "\n",
    "\n",
    "\n",
    "In our example, since $\\textit{r}$ = 12 and $\\textit{N}$ = 35 ;\n",
    "\n",
    "<center>then $\\textit{a}^\\textit{r/2}+1 = 3^{12/2} - 1 = 728$</center>\n",
    "\n",
    "<center>and $\\textit{a}^\\textit{r/2}+1 = 3^{12/2} + 1 = 730$.</center>\n",
    "\n",
    "<center>Therefore, $\\textit{p}$ = GCD(35, 728) = 7</center>\n",
    "\n",
    "<center>and $\\textit{q}$ = GCD(35, 730) = 5.</center>\n",
    "\n",
    "\n",
    "If you have read all the steps carefully, you will find that Step 3 is the elephant in the room. Since in real world scenarios, $\\textit{N}$ will be so large that it is impossible to calculate $\\textit{a}^x \\textit{Mod N}$ for $\\textit{x}$ ranging from 0 to $\\textit{Q}$ -1 without waiting for billions of years even with the most powerful supercomputers. This is where quantum computers will come to our rescue.\n",
    "\n",
    "<img src=\"img/6-g001.png\" >\n",
    "\n",
    "We have a quantum circuit that calculates $\\textit{a}^x  Mod  \\textit{N}$ for any given $\\textit{x}$. Though it is not easy to create such a circuit, it is possible because we know that any classical circuit can be converted to a quantum circuit using Toffoli gates. Instead of inputting each value of $\\textit{x}$ separately, we will give all the possible values of $\\textit{x}$ to the circuit by taking $\\textit{q}$ qubits and applying H gates on all of them. The input $\\textit{q}$ qubits will be in an equal superposition of |0⟩ to |$\\textit{Q}$− 1 ⟩. The bottom output qubits will be in a superposition of all the possible outputs $|\\textit{a}^0 \\textit{Mod N}⟩ to |\\textit{a}^{\\textit{Q}-1} \\textit{Mod N}⟩$.\n",
    "\n",
    "The system will be something like this (ignoring the normalization coefficients):\n",
    "\n",
    "<center>$|0⟩|\\textit{a}^0 \\textit{Mod N}⟩ + |1⟩|\\textit{a}^1 \\textit{Mod N}⟩ + |2⟩|\\textit{a}^2 \\textit{Mod N}⟩ ... |\\textit{Q}− 1 ⟩|\\textit{a}^{\\textit{Q-1}} \\textit{Mod N}⟩$.</center>\n",
    "\n",
    "Note that for multiple input qubit states there will be a common output state because $\\textit{a}^\\textit{x} \\textit{Mod N}$ is a many-to-one function. Now, if we go ahead and measure the output qubits, out of several superimposed outputs, only one of it will be obtained. Also, the input states will be affected in such a way that only those states that could result in the measured output can remain. The probabilities of all the other states will become zero.\n",
    "\n",
    "\n",
    "\n",
    "From Table 5.1, we can conclude that all the states that will be present in the input qubits will be separated by $\\textit{r}$. You must have noticed that we are closer to getting the answer because all we need is $\\textit{r}$ and we executed the circuit only once (exponential improvement must be obvious by now). But measuring the $\\textit{q}$ qubits will not help much because we don't have any pattern yet to exploit. Moreover, the first residue state might not be 0 and could be anything (called offset).\n",
    "\n",
    "Next, we do something called Inverse quantum Fourier Transform ($\\textit{QFT}$), it does the following:\n",
    "    1. It removes the offset and gives some probability for state 0\n",
    "    2. It changes the period between the states from $\\textit{r}$ to $\\textit{Q/r}$\n",
    "\n",
    "Now, if we measure the input $\\textit{q}$ qubits we are sure that we will get some multiple of $\\textit{Q/r}$ say $\\textit{L}$ ∗ $\\textit{Q/r}$. The value we measured is $\\textit{v}$, so we get the following equation:\n",
    "\n",
    "<center>$\\textit{v}$ = $\\textit{L}$ ∗ $\\textit{Q/r}$.</center>\n",
    "\n",
    "Rewritten as\n",
    "\n",
    "<center>$\\textit{v/Q}$ = $\\textit{L}$(1/$\\textit{r}$).</center>\n",
    "\n",
    "Here, we know the values of $\\textit{v}$ and $\\textit{Q}$. We can divide them until we get the smallest fraction. Now, the denominator will either be $\\textit{r}$ or a factor of $\\textit{r}$.\n",
    "\n",
    "Further details on $\\textit{QFT}$ and the circuit implementation can be found here:\n",
    "\n",
    "https://en.wikipedia.org/wiki/Quantum_Fourier_transform\n",
    "\n",
    "The actual circuit for the $\\textit{a}^x \\textit{Mod N}$ is beyond the scope of this book and a dedicated reader can get some help over here:\n",
    "\n",
    "https://arxiv.org/abs/quant-ph/0205095"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.7.6 64-bit ('quantum': conda)",
   "name": "python37664bitquantumconda24f1e788a28742df87643f332a236def"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
